#include "UnionFind.h"

element* makeSet (void *data)
{
    element *retVal = NULL;

    retVal = (element *)malloc(sizeof(element));
    retVal->data = data;
    retVal->rank = 0;
    retVal->leader = retVal;

    return retVal;
}
Ufds* UF_alloc (size_t size) {
	int i;
	Ufds *ds = (Ufds*) malloc (sizeof (Ufds));
	ds->size = size;
	ds->sets = (element**) malloc (sizeof (element*) * size);
	for (i = 0; i < size; i++) {
		ds->sets [i] = makeSet ((void*)i);
	}
	return ds;
}

int UF_dealloc (Ufds *ds) {
	int i;
	for (i = 0; i < ds->size; i++) {
		free (ds->sets[i]);
	}
	free (ds->sets);
	free (ds);
	return 0;
}


static element* find (element *e)
{
    while (e != e->leader) {
        //e->leader = find(e->leader);
		e = e->leader;
	}
    return e;
}

int UF_find (Ufds *ds, int x) {
	element *e, *root;
	e = ds->sets [x];
	root = find (e);
	return (int)root->data;
}

static void setUnion (element *x, element *y)
{
    element *leaderX = find(x);
    element *leaderY = find(y);
    if (leaderX->rank > leaderY->rank)
        leaderY->leader = leaderX;
    else {
        leaderX->leader = leaderY;
        if (leaderX->rank == leaderY->rank)
            ++(leaderY->rank);
    }
}

void UF_union (Ufds *ds, int x, int y) {
	element *ex, *ey;
	ex = ds->sets [x];
	ey = ds->sets [y];
	setUnion(ex, ey);
}
